﻿// Principia
// Copyright (C) 2008 Blake Hegerle
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#define Cache

using System.Collections.Generic;
using System.Linq;

namespace Principia.Core.Parsing.ContextFree.LR
{
    using Memo = Dictionary<ISymbol, IEnumerable<ITerminal>>;

    public sealed class ParserFactory
    {
        public static ParserFactory<V> New<V>(Grammar<V> Grammar)
        {
            return new ParserFactory<V>(Grammar);
        }
    }

    public class ParserFactory<T>
    {
        private readonly Dictionary<Tuple<ItemSet, ISymbol>, ItemSet> GotoMemo;
        private readonly INonterminal[] Nontermainals;
        private readonly Production[] Productions;
        private readonly ITerminal[] Terminals;
        private ParserState[] stateArray;

        public ParserFactory(Grammar<T> Grammar)
        {
            AssertNoDuplicateSymbolsInGrammar(Grammar);

            // Augment the grammar
            var AugmentedStart = new Nonterminal<T>(Grammar.StartSymbol.Name + '\'');
            AugmentedProduction = AugmentedStart.add(Grammar.StartSymbol, s => s);
            this.Grammar = new Grammar<T>(AugmentedStart);

            // Initial item
            InitialItem = new Item(0, AugmentedProduction, null);

            // Helper for Goto() method
            GotoMemo = new Dictionary<Tuple<ItemSet, ISymbol>, ItemSet>();

            // Flatten the symbol and production lists
            Productions = (from N in this.Grammar.Nonterminals
                           from P in N.Productions
                           select P).ToArray();
            Mark(Productions);
            Terminals = this.Grammar.Terminals.Union(new ITerminal[] { null }).ToArray();
            Mark(Terminals);
            Nontermainals = this.Grammar.Nonterminals.ToArray();
            Mark(Nontermainals);
        }

        public Production AugmentedProduction { get; private set; }
        public Grammar<T> Grammar { get; private set; }
        public Item InitialItem { get; private set; }

        public IEnumerable<ItemSet> ItemSets
        {
            get
            {
                var Collection = new Set<ItemSet>();

                var NewSets = new List<ItemSet> { Closure(InitialItem) };

                while (NewSets.Count > 0)
                {
                    foreach (var Set in NewSets)
                        Collection.Add(Set);

                    var WorkingSets = NewSets;
                    NewSets = new List<ItemSet>();

                    foreach (var Set in WorkingSets)
                    {
                        foreach (var X in Grammar.Symbols)
                        {
                            var G = Goto(Set, X);

                            if (G.Count > 0 && Collection.Contains(G) == false)
                                NewSets.Add(G);
                        }
                    }
                }

                return Collection;
            }
        }

        // This is the first of the two parser tables: the action table tells the parser whether to shift or reduce
        public Action[,] ActionTable
        {
            get
            {
                // First we must number the ItemSets
                var States = StateArray;

                var table = new Action[States.Length, Terminals.Length];

                for (var StateIndex = 0; StateIndex < States.Length; StateIndex++)
                {
                    var ItemSet = States[StateIndex].ItemSet;

                    for (var TerminalIndex = 0; TerminalIndex < Terminals.Length; TerminalIndex++)
                    {
                        var Terminal = Terminals[TerminalIndex];

                        // Set a variable indicating whether a shift is possible
                        var Shift = ItemSet.Any(Item => Item.ShouldShift(Terminal));

                        // Find all of the productions we _could_ reduce by
                        var ReduceProductions = from State in ItemSet
                                                where State.ShouldReduce(Terminal)
                                                select State.Production;

                        var ReduceCount = ReduceProductions.Count();
                        var Reduce = ReduceCount > 0;

                        // Check for error
                        if (Shift && Reduce)
                            throw new ShiftReduceException(Terminal, ReduceProductions);

                        var Action = new Action(ActionType.Error, 0);

                        // Set the shift action-table entry
                        if (Shift)
                        {
                            var GotoState = GotoId(ItemSet, Terminal);

                            Action = new Action(ActionType.Shift, GotoState);
                        }

                        // Set the reduce action-table entry
                        if (Reduce)
                        {
                            if (ReduceCount > 1)
                                throw new ReduceReduceException(ReduceProductions);

                            var ReduceBy = ReduceProductions.First();

                            // It's a reduction by S' -> S, which signals acceptance
                            if (ReduceBy == AugmentedProduction)
                            {
                                Action = new Action(ActionType.Accept, 0);
                            }
                            else
                            {
                                // It's a normal production
                                Action = new Action(ActionType.Reduce, ReduceBy.Id);
                            }
                        }

                        table[StateIndex, TerminalIndex] = Action;
                    }
                }

                return table;
            }
        }

        /* The goto table is the second of the two parser tables; it tells the parser what state to go to
         * after a reduction. */

        public int[,] GotoTable
        {
            get
            {
                var ParserStates = StateArray;

                var table = new int[ParserStates.Length, Nontermainals.Length];

                for (var sIndex = 0; sIndex < ParserStates.Length; sIndex++)
                    for (var nIndex = 0; nIndex < Nontermainals.Length; nIndex++)
                        table[sIndex, nIndex] = GotoId(ParserStates[sIndex].ItemSet, Nontermainals[nIndex]);

                return table;
            }
        }

        private ParserState[] StateArray
        {
            get
            {
                if (stateArray == null)
                {
                    var Id = 0;

                    var StateList = new List<ParserState>();
                    foreach (var ItemSet in ItemSets)
                        StateList.Add(new ParserState { Id = Id++, ItemSet = ItemSet });

                    stateArray = StateList.ToArray();
                }

                return stateArray;
            }
        }

        public IParser<T> MakeParser()
        {
            return new Parser<T>(Terminals.Length - 1, Productions, ActionTable, GotoTable);
        }

        // For a symbol S define FIRST(S) as the set of terminals a such that S ->* abc...
        // I.e. S derives a string starting with a.
        public IEnumerable<ITerminal> First(ISymbol Symbol)
        {
            return First(Symbol.Singleton());
        }

        public IEnumerable<ITerminal> First(IEnumerable<ISymbol> Symbols)
        {
            return FirstString(Symbols, new Memo()).Distinct();
        }

        private static IEnumerable<ITerminal> FirstSymbol(ISymbol S, Memo Memo)
        {
            IEnumerable<ITerminal> Result;

            if (Memo.TryGetValue(S, out Result))
                return Result;

            Memo[S] = new ITerminal[0];

            if (S is ITerminal)
            {
                var T = S as ITerminal;

                Result = T.Singleton();
            }
            else
            {
                if (S is INonterminal)
                {
                    var N = S as INonterminal;

                    Result = (from P in N.Productions
                              select FirstString(P.Symbols, Memo)).ConcatAll().ToList();
                }
            }

            Memo[S] = Result;

            return Result;
        }

        private static IEnumerable<ITerminal> FirstString(IEnumerable<ISymbol> String, Memo Memo)
        {
            var FirstSet = new Set<ITerminal>();

            foreach (var S in String)
            {
                var sFirst = FirstSymbol(S, Memo).ToList();

                var Epsilon = false;
                foreach (var f in sFirst)
                    if (f == null)
                        Epsilon = true;
                    else
                        FirstSet.Add(f);

                if (!Epsilon)
                    return FirstSet;
            }

            const ITerminal EpsilonTerm = null;

            return FirstSet.Concat(EpsilonTerm.Singleton());
        }

        public ItemSet Closure(Item Item)
        {
            var ItemSet = new ItemSet { Item };

            return Closure(ItemSet);
        }

        public ItemSet Closure(ItemSet StartingSet)
        {
            var NewItems = StartingSet.ToList();

            var Set = new Set<Item>();

            foreach (var Start in StartingSet)
                Set.Add(Start);

            while (NewItems.Count != 0)
            {
                IEnumerable<Item> WorkingItems = NewItems;

                NewItems = new List<Item>();

                foreach (var I in WorkingItems)
                {
                    var N = I.NonterminalAtPosition;

                    if (N != null)
                        foreach (var LA in First(I.SymbolsAfterPosition))
                            foreach (var P in N.Productions)
                            {
                                var NewItem = new Item(0, P, LA);

                                if (Set.TryAdd(NewItem))
                                    NewItems.Add(NewItem);
                            }
                }
            }

            var ItemSet = new ItemSet();

            foreach (var i in Set)
                ItemSet.Add(i);

            return ItemSet;
        }

        /* This is the bulk of the transition function. Note that this gets encoded
         * into the goto _table_ when actually executing a parser.
         */

        public ItemSet Goto(ItemSet ItemSet, ISymbol Symbol)
        {
            ItemSet GotoSet;

#if Cache
            //ItemSet = new ItemSet(ItemSet);

            var MemoArg = Tuple.New(ItemSet, Symbol);

            if (GotoMemo.TryGetValue(MemoArg, out GotoSet))
                return GotoSet;
#endif

#if trace
            Console.WriteLine("Computing new goto set");
#endif
            var GotoList = new ItemSet();

            foreach (var I in ItemSet)
            {
                if (I.Position < I.Production.Symbols.Length && I.Production.Symbols[I.Position] == Symbol)
                    GotoList.Add(new Item(I.Position + 1, I.Production, I.Lookahead));
            }

            GotoSet = GotoList.Count > 0 ? Closure(GotoList) : new ItemSet();

#if Cache
            GotoMemo[MemoArg] = GotoSet;
#endif

            return GotoSet;
        }

        // The collection of item-sets is isomorphic to (and used to construct) the set of parser states.

        private int GotoId(ItemSet ItemSet, ISymbol Symbol)
        {
            var GotoSet = Goto(ItemSet, Symbol);

            var State = (from S in StateArray
                         where S.ItemSet.Equals(GotoSet)
                         select S).FirstOrDefault();

            return State == null ? -1 : State.Id;
        }

        private static void Mark(Identified[] Objects)
        {
            for (var i = 0; i < Objects.Length; i++)
            {
                var o = Objects[i];
                if (o != null)
                    o.Id = i;
            }
        }

        private static void AssertNoDuplicateSymbolsInGrammar(Grammar<T> Grammar)
        {
            foreach (var Symbol in Grammar.Symbols)
            {
                var Name = Symbol.Name;
                var Count = Grammar.Symbols.Count(S => S.Name == Name);

                if (Count > 1)
                    throw new ParserConstructionException("There are two symbols named " + Symbol.Name);
            }
        }
    }
}